
\section{Introduction and Motivation}

The design of an embedded system requires different conflicting
objectives (energy consumption, performance, area) to be fulfilled.
In addition, it has to cope with an increasing demand and a reduced time-to-market~\cite{wsts}.
In many real cases, no analytical results are known to predict the relation between
system configurations and objectives. In such cases a high level
system simulation is the only way to have a picture of how system
parameters impact on the objectives.  A key problem is that the size
of the design space to be simulated grows with the product of
cardinalities of each parameter, resulting in an intractable number
of simulations. 

In these cases a Design Space Exploration (DSE) strategy is required,
i.e. an algorithm that selects only a tractable subset of all possible
configurations.  The final result of a design space exploration is a
subset of configurations called \emph{Pareto set} (\cite{pareto},
see also \defR{pareto-set}). The set of the corresponding tuples of objective values is called \emph{Pareto front}: it represents the trade-off between objectives,
i.e.  for each point of the Pareto front there is no other
configuration performing better for all the objectives (see
\figR{psos}).
%while providing, at the end, configurations that are close to the
%optimum and that are worth evaluating, in a following step of the
%design process, in a more thorough way.


In this work we present PS, a multi-objective design exploration
algorithm that introduces the concept of \emph{interesting} and
\emph{uninteresting regions} of the configuration space.  The main
idea can be simplified as follows: at each iteration of the algorithm,
the configuration space is divided in regions. A score is given to
each region based on the \emph{innovation} provided by its
configurations in the Pareto front, i.e. how different these configurations are, in terms of objective values, with respect to the ones previously found. The regions with high score are considered the most \emph{interesting} and, at the next iteration, more configurations are simulated there, rather than in the rest of the configuration space.
Several geometrical transformations (splitting, merging etc.) are
involved in the Parameter Space (aka configuration space), hence
the name PS for the algorithm.

From a more abstract but interesting perspective, the proposed
algorithm mimics the attention shift in human beings. For example,
authors in \cite{attention} models human attention as a single
resource with a limited budget that must be distributed among tasks,
preferring the task which the focus is on.  Authors in
\cite{spatial_attention} describe the visual attention as a spotlight
that focuses, each time, on a particular region of the visual space in
order to deeply process it. Similarly, PS focuses its
``spotlight'' only on the interesting regions and thoroughly explore them distributing the simulation budget on them.
% Ispirzione: http://en.wikipedia.org/wiki/Attentional_shift
In other words, with PS we propose a new perspective on the configuration space,
where parameter interdependencies play the fundamental role of making
some regions more capable of generating hardly predictable solutions:
catching this sort of ``chaoticity'' in the parameter space is the
main idea behind the strategy that is being introduced in this work.


The paper is organized as follows. First, \secR{Related-work} places our work in the context of related effort.
Then we give a theoretical formulation of the algorithm. In particular, in \secR{statement_of_the_problem} we provide formal definitions of the concepts and the operations that will be used to describe PS algorithm. In \secR{algorithm} we give the theoretical description of PS. 
Finally in \secR{ee} we show a case
study involving the exploration of the hardware/software parameters of
a Very Long Instruction Word (VLIW) architecture, performing a
qualitative and quantitative comparison of PS against the state-of-the-art
of multi-objective genetic based approaches.


\section{Related work and Our Contribution}
\secL{Related-work}
Many different design space exploration algorithms have been proposed
in literature. Exploring the design space of embedded systems is difficult not only because of the huge size of the parameter space, but also due to the tight \emph{dependencies} between parameters, which impact the objectives.
Due to this complexity, exploration algorithms are usually heuristic and, to a large extent, rely on simple intuitions rather then formal arguments.

Some exploration strategies assume some knowledge about the
system parameters, their semantics and their impact on design
objectives.  The \emph{Dependency analysis}, proposed in
\cite{givargis_tvlsi02}, is meant to take advantage of the parameter
dependencies. A ``dependency graph'' is constructed and clusters -- i.e. subsets of strongly dependency-connected parameters -- are recognized. Each cluster is exhaustively evaluated and its ``local''
Pareto set is found. Then, all local Pareto sets are merged. In this
way, a series of local exhaustive evaluations are performed instead of
an exhaustive evaluation of all the possible configurations. Some
problems arise: i) In real scenarios, parameter interdependencies may be so deep that it may be difficult to recognize independent clusters. This may lead to
the need of an evaluation of almost all the possible configurations.
ii) A designer may not have a precise and complete a-priori picture of
the dependencies among parameters; for this reason the need of
``automated approaches for computing interdependencies'' is declared
in the same paper.  These drawbacks are not present in PS,
since, although it leverages dependencies as in
\cite{givargis_tvlsi02}, it is able to detect them automatically, requiring no a-priori knowledge. Moreover, our algorithm is able to
capture also ``local dependencies", i.e. dependencies that emerge only
among certain ranges of parameters and may not hold when considering
the entire ranges. This cannot be modeled in Dependency Analysis. 

A preliminary estimation of hardware/software dependencies in order to
reduce the exploration of the design space is addressed in~\cite{Catania2008}, where
authors propose to deal with the software parameters separately,
statistically testing their average effect on objectives before the
actual exploration is performed. Also in~\cite{merging} authors
analyze the impact of including compilation parameters into the design
space exploration. The results of both works confirm the
important role that hardware/software dependencies play in a
multi-objective exploration and thus justify the choice of explicitly
including the two classes of parameters in the design space without
making any distinction between them from the algorithm's perspective.
In fact, one of the purposes of the proposed PS algorithm is to avoid
the need of any a priori knowledge about those dependencies, letting
the algorithm itself discover regions where interaction among
parameters generates new Pareto-optimal points (see the PS scoring
system described in the next sections).

Abraham, Rau and Schreiber proposed in \cite{santosh_hptr00} to
decompose the system under evaluation into components that minimally interact with each other. Pareto sets for each component are found
and, provided that ``monotonicity'' exists, the complete Pareto set is
computed merging the component Pareto sets. Roughly speaking (see
section 4 of the same paper for more details), monotonicity property
guarantees that the best system can be obtained as a composition of
the best components. This approach would perfectly work if all the
components were perfectly isolated, i.e., if there were no
dependencies among them. But real scenarios rarely expose monotonicity
property, and thus inaccuracies may occur, as stated in the same paper.

Other approaches, as \cite{fornaciari_codes01,palesi_iwsoc02}, are
based on the concept of \emph{sensitivity analysis}, i.e. measuring
how much the objective varies when varying each parameter.  Parameters
are ordered based on their sensitivity. The first parameter (the most
sensitive one) is varied, while keeping the other parameters fixed to
arbitrary values, and its best value is found. The same procedure is repeated for the second parameter and so on. The limited accuracy
shown by these approaches can be explained by the limited and rigid
exploration of the parameter space: after fixing the best first
parameter value, there are no more chances to consider different
values. It is worth noticing that this approach can not capture
``local sensitivity'', i.e. the objectives may be more sensitive to
some ranges of a parameter and less sensitive to other ranges of the
same parameter. Moreover, it can not capture ``combined sensitivity'',
i.e. the objectives may be more sensitive to a range of a parameter
$p_{1}$, only when other parameters are within certain ranges, and
less sensitive to the same range of $p_{1}$ when the other parameters
are in different ranges. On the contrary, our algorithm can capture
both local and combined sensitivity.

Authors of \cite{dellnitz2005covering,dellnitz2009computation} propose
three different methods for the numerical approximation of the Pareto
set. The first two require the knowledge of the gradient of the
objective functions, which is usually not available in embedded system
design, since the closed form expression of the objective functions is
not known a priori. The third one, called ``Sampling algorithm'', does
not need this requirement and is the closest to the PS approach
presented in this work, although the
mechanism is different. At every iteration a set of regions of
configuration space is constructed with the aim to cover the Pareto
set. The size of these regions becomes smaller at each iteration so
that the covering becomes tighter. A random set of test points are
evaluated in each new region; only the regions containing
non-dominated points will be considered in the next iteration.
An important feature differentiates it from PS. In the Sampling algorithm only the
selected regions are examined, even though there is no guarantee that
they contain all the Pareto points. As a consequence, the
Sampling algorithm may erroneously and prematurely neglect some
regions that may possibly contain a non-negligible number of Pareto
points. The PS algorithm avoids this, since even though a region has not
provided non-dominated points, it is not neglected, but it is
populated with fewer test points, allowing to
find its other non-dominated points. From this behavior also comes
another important difference. The Sampling algorithm of
\cite{dellnitz2005covering} keeps reinforcing the analysis of the
regions selected in the previous iterations. In other words, it keeps
zooming in on the regions that have been considered ``interesting'',
i.e. rich of non-dominated points, in the previous iterations. The
philosophy behind our algorithm is different. A region, which has been
considered interesting at certain iterations, may not be in the
future, since it has been thoroughly analyzed. On the other hand, a
region, initially uninteresting, may turn out to be interesting in the
future, once all the other regions have been already exploited.
Therefore, from an iteration to the next, our algorithm zooms in on
regions that are currently interesting and zooms out from the
uninteresting ones,  spanning in a broader and more dynamical way the
configuration space. In addition, in the Sampling algorithm only the
number of non-dominated points is accounted to see how interesting a
region is. On the contrary, we also consider the \emph{innovation}, as
already anticipated in the introduction.

The most well documented and widespread class of algorithms adopted in the
design space exploration of embedded systems is represented by the Evolutionary
Multi-objective Optimization Algorithms~\cite{coello_easmop}. For this
reason, this is the class of algorithms that we will compare to ours in the experiments of~\secR{ee}.
Evolutionary approaches have many advantages: they provide good accuracy, they are
problem-independent and do not require any a-priori knowledge of the
system. The strong point of these approaches is that they consist in an exploration that is sufficiently broad
(the mutation avoids being rigidly restricted to limited parts of
parameter space), and, at the same time, not too scattered, as it is
guided by the performances of the already evaluated configurations.
Different variants of these algorithms have been proposed in
literature, including mixed approaches as in~\cite{Ascia2011382},
where authors specifically focus on increasing the performance of an
evolutionary exploration strategy, proposing a fuzzy-based technique
to avoid the actual simulation of a certain number of configurations.
In particular, in this work we will compare the proposed approach against a
well known SPEA2 multi-objective genetic algorithm~\cite{knowles_techrep06}
which is, to the best of our knowledge, one of the most appropriate and
tested for the particular scenario we are assuming.  We
claim that the approach presented in this paper has most of the
benefits of the evolutionary approaches, although the rationale is
completely different.
